package com.snopy.leetcode.index1_1000.index101_200;

import java.util.Random;

/**
 * @author snopy
 * @version 1.0.0
 * @classname Question169
 * @description 多数元素
 * 给定一个大小为 n 的数组nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于⌊ n/2 ⌋的元素。
 *
 * 你可以假设数组是非空的，并且给定的数组总是存在多数元素。
 *
 * 示例1：
 *
 * 输入：nums = [3,2,3]
 * 输出：3
 * 示例2：
 *
 * 输入：nums = [2,2,1,1,1,2,2]
 * 输出：2
 * @email 77912204@qq.com
 * @date 2022/05/10 0:29
 */
public class Question169 {

    public static void main(String[] args) {
        int[] nums = new int[]{2,2,1,1,1,2,2,1,1};
        int num = new Question169().majorityElement(nums);
        System.out.println(num);
    }
    private int randNum(Random rand,int min,int max){
        return rand.nextInt(max-min)+min;
    }
    private int countOccurences(int[] nums,int num) {
        int count = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == num){
                count++;
            }
        }
        return count;
    }
    public int majorityElement(int[] nums) {
        Random random = new Random();
        int majorityCount = nums.length/2;
        while (true){
            int candidate = nums[randNum(random,0,nums.length)];
            if (countOccurences(nums,candidate) > majorityCount){
                return candidate;
            }
        }
    }

}
